package org.example.day;

import java.util.Arrays;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/06/08 20:59
 */
public class Solution3040 {

    int[] nums;
    int[][] memo;

    public static void main(String[] args) {
        Solution3040 solution = new Solution3040();
        System.out.println(solution.maxOperations2(new int[]{1,1,2,3,2,2,1,3,3}));
    }

    public int maxOperations(int[] nums) {

        int[] scores = new int[3];
        scores[0] = nums[0] + nums[1];
        scores[1] = nums[0] + nums[nums.length-1];
        scores[2] = nums[nums.length-2] + nums[nums.length-1];

        int max = 0;

        for(int score : scores){
            int end = nums.length;
            int subMax = 0;
            for (int i = 0; i < end; i++) {
                if((i+1 < end) && (score == nums[i] + nums[i+1])){
                    i++;
                    subMax++;
                }else if(score == nums[i] + nums[end-1]){
                    end--;
                    subMax++;
                }else if((i <= end-2) && (score == nums[end-2] + nums[end-1])){
                    end-=2;
                    i--;
                    subMax++;
                }else{
                    break;
                }
            }
            max = Math.max(max, subMax);
        }

        return max;
    }


    public int maxOperations2(int[] nums) {
        int n = nums.length;
        this.nums = nums;
        this.memo = new int[n][n];
        int res = 0;
        res = Math.max(res, helper(0, n - 1, nums[0] + nums[n - 1]));
        res = Math.max(res, helper(0, n - 1, nums[0] + nums[1]));
        res = Math.max(res, helper(0, n - 1, nums[n - 2] + nums[n - 1]));
        return res;
    }

    public int helper(int i, int j, int target) {
        for (int k = 0; k < nums.length; k++) {
            Arrays.fill(memo[k], -1);
        }
        return dfs(i, j, target);
    }

    public int dfs(int i, int j, int target) {
        if (i >= j) {
            return 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        int ans = 0;
        if (nums[i] + nums[i + 1] == target) {
            ans = Math.max(ans, dfs(i + 2, j, target) + 1);
        }
        if (nums[j - 1] + nums[j] == target) {
            ans = Math.max(ans, dfs(i, j - 2, target) + 1);
        }
        if (nums[i] + nums[j] == target) {
            ans = Math.max(ans, dfs(i + 1, j - 1, target) + 1);
        }
        memo[i][j] = ans;
        return ans;
    }

}


